//
// Created by Administrator on 2021/8/6.

//存在一个由 n 个节点组成的无向连通图，图中的节点按从 0 到 n - 1 编号。
//
//给你一个数组 graph 表示这个图。其中，graph[i] 是一个列表，由所有与节点 i 直接相连的节点组成。
//
//返回能够访问所有节点的最短路径的长度。你可以在任一节点开始和停止，也可以多次重访节点，并且可以重用边。
//
//
//来源：力扣（LeetCode）
//链接：https://leetcode-cn.com/problems/shortest-path-visiting-all-nodes
//著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
#include <vector>
#include <iostream>
#include <algorithm>
#include <queue>
#include <unordered_map>
#include <unordered_set>
#include <string>
#include <climits>
using namespace std;

class Solution {
public:
    /**
     * 找到一条可以连通所有点的最短路径
     * 起点怎么确定？
     * 由于题目需要我们求出「访问所有节点的最短路径的长度」，并且图中每一条边的长度均为 1
     * ，因此我们可以考虑使用广度优先搜索的方法求出最短路径。
    在常规的广度优先搜索中，我们会在队列中存储节点的编号。对于本题而言，最短路径的前提是「访问了所有节点」，
     因此除了记录节点的编号以外，我们还需要记录每一个节点的经过情况。
     因此，我们使用三元组 (u,mask,dist) 表示队列中的每一个元素，其中：
    u 表示当前位于的节点编号；
    mask 是一个长度为 n 的二进制数，表示每一个节点是否经过。如果mask 的第 i 位是 1，
    则表示节点 i 已经过，否则表示节点 i 未经过；
    dist 表示到当前节点为止经过的路径长度。
    这样一来，我们使用该三元组进行广度优先搜索，即可解决本题。初始时，我们将所有的 (i, 2^i, 0)放入队列，
    表示可以从任一节点开始。在搜索的过程中，如果当前三元组中的 mask 包含 n 个 1（即 mask = 2^n - 1，
    那么我们就可以返回 dist 作为答案。
     *
     * @param graph
     * @return
     */
    int shortestPathLength(vector<vector<int>> &graph) {
        // 节点总数
        int n = (int) graph.size();
        // bfs队列
        queue<tuple<int, int, int>> q;
        // 记录是否经过
        vector<unordered_set<int>> seen(n);
        for (int i = 0; i < n; ++i) {
            q.emplace(i, 1 << i, 0); // 放入初始值  每个节点都可以作为起始点
            seen[i].insert(1 << i);
        }
        int ans = 0;
        while (!q.empty()) {
            auto[u, mask, dist] = q.front();
            q.pop();
            if (mask == (1 << n) - 1) { // 找到答案
                ans = dist;
                break;
            }
            // 搜索相邻节点
            for (auto v:graph[u]) {
                //将mask的第v位置为1
                int mask_v = mask | (1 << v);
                if (!seen[v].count(mask_v)) {
                    q.emplace(v, mask_v, dist + 1);
                    seen[v].insert(mask_v);
                }
            }
        }
        return ans;
    }
};
class Solution2   {// 预处理点对间最短路 + 状态压缩动态规划
public:
    int shortestPathLength(vector<vector<int>>& graph) {
        int n = graph.size();
        vector<vector<int>> d(n, vector<int>(n, n + 1));
        for (int i = 0; i < n; ++i) {
            for (int j: graph[i]) {
                d[i][j] = 1;
            }
        }
        // 使用 floyd 算法预处理出所有点对之间的最短路径长度
        for (int k = 0; k < n; ++k) {
            for (int i = 0; i < n; ++i) {
                for (int j = 0; j < n; ++j) {
                    d[i][j] = min(d[i][j], d[i][k] + d[k][j]);
                }
            }
        }
        // 看不懂了
        vector<vector<int>> f(n, vector<int>(1 << n, INT_MAX / 2));
        for (int mask = 1; mask < (1 << n); ++mask) {
            // 如果 mask 只包含一个 1，即 mask 是 2 的幂
            if ((mask & (mask - 1)) == 0) {
                int u = __builtin_ctz(mask);
                f[u][mask] = 0;
            }
            else {
                for (int u = 0; u < n; ++u) {
                    if (mask & (1 << u)) {
                        for (int v = 0; v < n; ++v) {
                            if ((mask & (1 << v)) && u != v) {
                                f[u][mask] = min(f[u][mask], f[v][mask ^ (1 << u)] + d[v][u]);
                            }
                        }
                    }
                }
            }
        }

        int ans = INT_MAX;
        for (int u = 0; u < n; ++u) {
            ans = min(ans, f[u][(1 << n) - 1]);
        }
        return ans;
    }
};


int main() {
    vector<vector<int>> graph{{1, 2, 3},
                              {0},
                              {0},
                              {0}};
    Solution2 solution;
    cout << solution.shortestPathLength(graph) << endl;
    return 0;
}
